package com.dong.binaryTree;

import java.util.*;

/**
 * 迭代实现三种遍历
 */


class TreeNode{
    int val;//存放值
    TreeNode left;//指向左节点
    TreeNode right;//指向右节点
    TreeNode(){};
    TreeNode(int val){
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * 那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，
 * 直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），
 * 这就造成了处理顺序和访问顺序是不一致的。
 * 那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。
 */
//中序遍历  左-中-右 入栈顺序： 左-右
public class InorderTraversal {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        //栈则用来处理节点上的元素
        Stack<TreeNode> stack = new Stack<>();
        //指针的遍历来帮助访问节点
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
            if (cur != null){// 指针来访问节点，访问到最底层
                stack.push(cur);// 将访问的节点放进栈
                cur = cur.left;//左
            }
            else{
                cur = stack.pop(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                result.add(cur.val);//中
                cur = cur.right;//右
            }
        }
        return result;
    }


    //前序遍历:中 左 右  入栈顺序：中 右 左
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return result;


    }

    //后续遍历   后序遍历顺序 左-右-中  前序：中-左-右  —>中-右-左 最后翻转结果为：左右中
    public List<Integer>postorder(TreeNode root){
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;

    }

}
